package com.ly.algorithm.DataStructures.tree;

/**
 * @Classname ThreadedBinaryTree
 * @Description TODO
 * @Date 2020/4/29 9:27
 * @Author 冷心影翼
 */
public class ThreadedBinaryTree {
    public Node tree;

    public Node pre;

    public Node preOrderSearch(int no) {
        if(tree!=null) {
            return tree.preOrderSearch(no);
        }else {
            return null;
        }
    }
    public Node infixOrderSearch(int no) {
        if(tree!=null) {
            return tree.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    public Node postOrderSearch(int no) {
        if(tree!=null) {
            return tree.postOrderSearch(no);
        }else {
            return null;
        }
    }

    public ThreadedBinaryTree(Node tree) {
        this.tree = tree;
    }

    public void preOrder() {
        if(tree!=null){
            tree.preOrder();
        }

    }

    public void infixOrder() {
        if(tree!=null){
            tree.infixOrder();
        }

    }

    public void postOrder() {
        if(tree!=null){
            tree.postOrder();
        }
    }

    public void delete(int no) {
        if(tree!=null) {
            tree.delete(no);
        }
        if(tree.no == no) {
            tree = null;
        }
    }

    public void threadedNodesPost(Node node) {
         if(node == null) {
             return;
         }
         threadedNodesPost(node.left);
         threadedNodesPost(node.right);
         if(node.left == null) {
             node.leftType = 1;
             node.left = pre;
         }
         if(pre!=null && pre.right == null) {
             pre.rightType = 1;
             pre.right = node;
         }
         pre = node;
    }

    public void threadedListPost(Node root) {
        Node node = root;
        pre = null;

        while (node != null && node.leftType == 0) {
            node = node.left;
        }


        while (node != null ) {
            if (node.rightType == 1) {
                System.out.println(node);
                pre = node;
                node = node.right;
            } else {
                if(node.right == pre) {
                    System.out.println(node);
                    if(node == root) {
                        return ;
                    }
                    pre = node;
                    node = node.parent;
                } else {
                    node = node.right;
                    while (node!=null && node.leftType == 0) {
                        node = node.left;
                    }
                }
            }
        }
    }

    public void threadedNodesPre(Node node) {
        if(node == null) {
            return;
        }
        threadedNodesPre(node.left);
        if(node.left == null ) {
            node.left = pre;
            node.leftType = 1;
        }

        if(pre!=null && pre.right == null) {
            pre.right = node;
            pre.rightType = 1;
        }

        pre = node;
        threadedNodesPre(node.right);
    }

    public void threadedListPre(Node root) {
        Node node = root;
        while (node!=null) {
            while (node.leftType == 0) {
                node = node.left;
            }
            System.out.println(node);

            while (node.rightType == 1) {
                node = node.right;
                System.out.println(node);
            }

            node = node.right;
        }
    }
}

class Test2 {

    public static void main(String[] args) {
        Node a = new Node(1, "a");
        Node b = new Node(3, "b");
        Node c = new Node(6, "c");
        Node d = new Node(8, "d");
        Node e = new Node(10, "e");
        Node f = new Node(14, "f");
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;

        b.parent = a;
        c.parent = a;
        d.parent = b;
        e.parent = b;
        f.parent = c;

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(a);
//        threadedBinaryTree.threadedNodesPre(a);
        threadedBinaryTree.threadedNodesPost(a);
//        System.out.println(a.left);
//        System.out.println(d.rightType);
        threadedBinaryTree.threadedListPost(a);
//        threadedBinaryTree.threadedListPre(a);
    }
}